#include <stdio.h> void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void Adjust(int *a, int parent, int high) { int l = 2 * parent + 1; int r = l + 1; int flag = parent; if (l<=high && a[l]>a[flag]) { flag = l; } if (r<=high && a[r]>a[flag]) { flag = r; } if (flag != parent) { swap(a[parent], a[flag]); Adjust(a, flag, high); } } void HeapSort(int *a, int n) { int i; for (i=n-1; i>=0; i--) { Adjust(a, i, n - 1); } for (i=n-1; i>=0; i--) { swap(a[0], a[i]); Adjust(a, 0, i - 1); } } void Output(int *a, int n) { int i; for (i=0; i<n; i++) { printf("\t%d", a[i]); } printf("\n"); } int main() { int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; int n = 8; Output(a, n); HeapSort(a, n); Output(a, n); return 0; } /* 49 38 65 97 76 13 27 49 13 27 38 49 49 65 76 97 Press any key to continue */
|